20241114

複雜度

用來判斷程式寫得好不好的依據之一
直覺判斷來說，程式跑得快，越有效率->寫得好；反之程式寫得不太好

複雜度又有分為時間與空間
時間複雜度:描述程式隨著輸入的增加，執行所需時間如何變化
像是訂票網站，訂票的時候網站一直轉圈圈
空間複雜度:描述程式隨著輸入的增加，占用的記憶體如何變化
在宣告變數的時候都會占用電腦的記憶體，然而電腦空間式有限的，如果太多資料會導致記憶體不足

如何描述複雜度呢

常見的BigO有下面幾種
O(1): 常數時間，與輸入大小無關
O(n): 線性時間，與輸入大小成正比
O(n平方): 平方時間，隨著輸入大小增加成平方增長
O(logn): 對數時間，隨著輸入大小增加而減慢增長速率
O(logn)是最好的方法

空間複雜度
固定空間
變動空間
(要補充)

資料結構

除了前面提到的變數、值之外，資料會有不同的組合方式來儲存，讓存取更有效率或方便閱讀。JAVA本身有內建一些資料結構，而 Array、List、Map、Set 是比較常見的資料結構

Array

特點:
固定大小: 一旦創建，大小就無法改變
隨機存取: 可以透過索引快速存取特定位置的元素
效率高: 在記憶體是連續位置上分配，存取效率高

int[] arr = new int[5]; //宣告一個陣列並設定大小
arr[0] = 11; //使用索引的方式取值

通常使用for、foreach迴圈方式取得所有值

List

是一個可遍大小有序集合，允許元素重複
常見的List有兩種
ArrayList:基於動態陣列
LinkedList:基於鏈結串列
特點:
有序:元素有明確的順序，可依索引存取
可變大小:可以動態增減元素
允許重複:可以有相同的元素

list.add(element);
list.get(index);
list.remove(index);

小比喻:
Array像是轎車，空間固定
List像是火車頭，空間可以透過車廂的數量增減來改變

ArrayList VS LinkedList

ArrayList:List物件裡面有一個Array，默認長度為10，記憶體為連續性，當長度超過原本大小時，透過List的特性，自動增加內部陣列的大小
通常增長的大小，以1.5倍的比例擴展陣列的容量

LinkedList:
記憶體不連續，透過node的方式去尋找

頻繁刪除物件:LinkedList(queue,stack)，使用原因，ArrayList雖然能夠自動增減大小但是在頻繁刪除增加的情況下會造成空間上的不必要性，而LinkedList則是透過node的方式尋找需要刪除的物件，在以空間上來說顯得更有效率
取得List中特定物件:ArrayList(search,sort)，使用原因，ArrayList是透過索引的方式取得值，因此不需要向LinkedList需要透過node來繁複尋找

實作這部分參考HISKIO-圖解演算法系列(JAVA)
https://hiskio.com/courses/465